聚集最近邻查询技术研究

【摘要】随着移动设备的不断普及，基于空间位置的查询服务已经逐渐渗入到人们生活的方方面面。无论是从欧式空间的查询研究到路网环境下的查询研究，还是从静态对象的查询研究到移动对象的查询研究，空间数据库查询已变得越来越多样化和复杂化。聚集最近邻(AggregateNeareastNeighbor,ANN)查询作为一种基于位置服务的空间查询技术，已经成为当前的一个研究热点问题。ANN查询检索的是到多个查询点距离的聚集函数值最小的目标对象，其查询结果依赖于确定的聚集函数。目前，ANN查询已经存在不少的研究成果，主要包括欧式空间和路网环境两个方面的研究，然而现有的路网环境下ANN查询算法存在空间检索范围大以及距离计算冗余多的问题。针对这些不足，本文首先提出了一种基于影响区域的ANN查询算法。考虑到大量查询位置同时发起查询请求且要求查询结果能够及时反馈的实际需求，本文接下来提出了一种基于影响区域的快速ANN查询算法。首先，分析了ANN查询本身的一些特性，并总结了网络Voronoi图在网络空间中计算距离的优势，引入了影响区域的基本概念，并且给出了相应的构建算法。接着，通过对基于Voronoi图的ANN查询算法的深入分析，本文给出了一种基于影响区域的ANN查询算法。该算法将Voronoi图和影响区域相结合，在缩小查询空间范围的同时也大大减少了距离的计算。而后，用真实的数据集分别对sum聚集函数和max聚集函数做了对比实验。实验验证了基于影响区域的ANN查询算法比基于Voronoi图的ANN查询算法具有更高的效率。最后，针对大量查询点数据的处理需求，引入了查询分组和查询代表点相关概念，并给出了一种基于影响区域的快速ANN查询算法。该算法是以牺牲查询结果的准确率来达到提高查询速度的目的。实验给出了查询分组和组内包含的查询点个数对该算法性能的影响。本文针对现有ANN查询算法中存在的不足，创新地提出了基于影响区域的ANN查询算法，从而能够获得较高的查询效率。另外，又以现实需求为驱动，给出了基于影响区域的快速ANN查询算法。总之，本文提出的ANN查询算法是对现有查询算法的改进。
【作者】张小菲；
【导师】徐建；
【作者基本信息】杭州电子科技大学，计算机应用技术，2014，硕士
【关键词】空间查询；聚集最近邻查询；Voronoi图；影响区域；

【参考文献】
[1]黄海舰.基于FPGA时间内插技术的TDC设计[D].华中师范大学,无线电物理,2013,硕士.
[2]吕向洋.颈动脉狭窄程度及血hs-CRP水平对缺血性脑血管事件的影响[D].第三军医大学,神经病学（专业学位）,2012,硕士.
[3]柯玲,周小佳.信息经济发展中的信息经济测度研究[J].电子科技大学学报(社科版),2005,04:14-18.
[4]杜宇.英若诚戏剧翻译理论在其《茶馆》英译本中的运用与体现[D].扬州大学,英语语言文学,2012,硕士.
[5]张敏慧.IDO、KYN在大鼠慢性脑低灌注所致认知障碍中的作用[D].山西医科大学,神经病学（专业学位）,2013,硕士.
[6]陈磊.微博图书出版现象研究[D].兰州大学,新闻与传播（专业学位）,2013,硕士.
[7]王小力,庞凯歌,刘卫华,李昕,田康,尹艳南,张娟.石墨烯折角场发射特性[J].光子学报,2014,11:7-11.
[8]邓俊蕾.基于双线性映射的代理签名与代理多重签名方案的研究[D].华东交通大学,应用数学,2013,硕士.
[9]李众,杨一栋.一种新的基于二维云模型不确定性推理的智能控制器[J].控制与决策,2005,08:866-872+877.
[10]程照星.数据挖掘在电信企业客户细分中的应用[D].重庆大学,2004.
[11]李斌.顾客价值管理理论在黑龙江移动呼叫中心的应用研究[D].四川大学,2004.
[12]王晓.面向Ad hoc网络的分布式空时编码技术研究[D].西安电子科技大学,通信与信息系统,2012,硕士.
[13]朱亚光.集成质量系统与标准化技术应用研究[D].大连理工大学,机械制造及其自动化,2004,硕士.
[14]张庆明.阻断水貂肠炎细小病毒感染F81细胞的多肽筛选与验证[D].吉林大学,动物营养与饲料科学,2013,硕士.
[15]邱勇.重金属离子和放射性核素在磁性海泡石上的吸附性能研究[D].合肥工业大学,化学工艺,2013,硕士.
[16]程绣.烧伤病房耐甲氧西林金黄色葡萄球菌（MRSA）和鲍曼不动杆菌（Ab）快速诊断及菌株同源性研究[D].苏州大学,病原生物学,2014,硕士.
[17]张文丽.一些双圈图的谱特征[D].新疆师范大学,应用数学,2013,硕士.
[18]张晓丽.汉语负迁移对高中英语写作的影响[D].辽宁师范大学,英语语言文学,2012,硕士.
[19]胡明光.社会冲突与公共政策变迁[D].复旦大学,行政管理,2012,硕士.
[20]卢振.微结构件的注射成形及其组织与性能[D].哈尔滨工业大学,2008.
[21]刘云龙.大间隙永磁轴流式血泵速度控制研究[D].中南大学,机械工程,2013,博士.
[22]王斌.图的笛卡尔积运算和张量积运算不变性研究及其应用[D].湖北工业大学,计算机应用技术,2013,硕士.
[23]王薇.地域文化在城市公园中的应用研究[D].云南农业大学,园林植物与观赏园艺,2013,硕士.
[24]解宁波.基于电动舵机的姿态测量控制技术研究[D].中北大学,火炮、自动武器与弹药工程,2013,硕士.
[25]SAP中国金融行业总经理栗树和博士.中国如何防范金融风险[N].计算机世界,2002-03-25C13.
[26]余文俊.我国产业集聚与区域差距关系研究[D].天津财经大学,区域经济学,2012,硕士.
[27]孟凡琨.基于QR码的车牌识别系统探索性研究[D].长安大学,交通信息工程及控制,2014,硕士.
[28]张郝.谈实践创作中对李可染山水画“墨法”的理解与运用[D].沈阳师范大学,美术,2013,硕士.
[29]王超.网络道德失范及建设探究[D].大连海事大学,马克思主义哲学,2014,硕士.
[30]乔能伟.基于内存数据库的国际业务结算系统研究与实现[D].湖南大学,软件工程,2011,硕士.
[31]钟秋.贺兰—六盘—鄂尔多斯西缘构造带地震速度扰动及泊松比成像[D].西北大学,地质工程（专业学位）,2014,硕士.
[32]吴俊雄.超负荷血糖对局灶性脑缺血再灌注皮质区Daxx、Endostatin表达的影响[D].遵义医学院,神经病学,2012,硕士.
[33]李琳.山西省晋城市住房公积金管理研究[D].山西财经大学,社会保障,2013,硕士.
[34]王璐.内蒙古农发行商业性贷款风险及其防范对策研究[D].内蒙古农业大学,农村与区域发展,2013,硕士.
[35]黄旭,刘建华,王慧明,朱慧勇,李志勇,滕理送.口内入路下颌骨良性肿瘤切除同期自体骨移植修复重建术的临床研究[J].中国修复重建外科杂志,2014,02:192-196.
[36]徐薇.自助餐服务系统的平面布置问题研究[D].吉林大学,交通运输工程,2013,硕士.
[37]冯夏庭,马平波.基于数据挖掘的地下硐室围岩稳定性判别[J].岩石力学与工程学报,2001,03:306-309.
[38]陈鲤江,郑云巧,孙晓梦.物理量单位的智能导出算法及其应用[J].大学物理实验,2013,03:63-65.
[39]于丽娟.电子文件管理系统的功能——基本功能及其功能拓展[J].北京档案,2002,10:18-20.
[40]刘继洪.人甲胎蛋白基因原核克隆和表达[D].浙江大学,内科学,2004,硕士.
[41]陶丽华,蔡燕,李在均,任国晓,刘俊康.石墨烯/CdS量子点复合材料的电化学性能研究[J].无机材料学报,2011,09:912-916.
[42]施青松,陈文智.强化计算机课程贯通教学深入面向系统能力培养[J].中国大学教学,2014,12:61-65.
[43]郭刚.自适应神经模糊控制策略在倒立摆系统中的研究[D].太原理工大学,控制理论与控制工程,2004,硕士.
[44]牛芳芳.关于三次域类数的研究[D].西南大学,基础数学,2013,硕士.
[45]魏玲玲.高灵敏度GPSL1/L2C软件接收机捕获算法研究[D].南京航空航天大学,精密仪器及机械,2013,硕士.
[46]胡绍谦,胡荣,张喜铭,王文龙,林青.智能远动机的研制[J].电力系统自动化,2014,09:119-124.
[47]刘上楼.胸腰段椎体采用漏斗技术与徒手技术置入椎弓根螺钉的生物力学比较[D].扬州大学,外科学,2012,硕士.
[48]杨斌,王金城.中立型一般Lurie系统绝对稳定的时滞相关准则[J].自动化学报,2004,02:261-264.
[49]张玉.协作通信中关于中继选择和功率分配的研究[D].杭州电子科技大学,通信与信息系统,2014,硕士.
[50]张琼.两种先行组织者（advance organizer）对中学生听力理解的影响：听前背景知识和词汇知识指导[D].西安外国语大学,外国语言学及应用语言学,2013,硕士.